Search for: All records

Linearity testing has been a focal problem in property testing of functions. We combine different known techniques and observations about Linearity testing in order to resolve two recent versions of this task. First, we focus on the online-manipulation-resilient model introduced by Kalemaj, Raskhodnikova and Varma (Theory of Computing 2023). In this model, up to t data entries are adversarially manipulated after each query is answered. Ben-Eliezer, Kelman, Meir, and Raskhodnikova (ITCS 2024) showed an asymptotically optimal Linearity tester that is resilient to t manipulations per query, but fails if t is too large. We simplify their analysis for the regime of small t, and for larger values of t we instead use sample-based testers, as defined by Goldreich and Ron (ACM Transactions on Computation Theory 2016). A key observation is that sample-based testing is resilient to online manipulations but still achieves optimal query complexity for Linearity when t is large. We complement our result by showing that when t is very large any reasonable property, and in particular Linearity, cannot be tested at all. Second, we consider Linearity over the reals with proximity parameter ε. Fleming and Yoshida (ITCS 2020) gave a tester using O(1/ε · log(1/ε)) queries. We simplify their algorithms and modify the analysis accordingly, showing an optimal tester that only uses O(1/ε) queries. This modification works for the low-degree testers presented in Arora, Bhattacharyya, Fleming, Kelman, and Yoshida (SODA 2023) as well, resulting in optimal testers for degree-d polynomials, for any constant d. 

Linearity testing has been a focal problem in property testing of functions. We combine different known techniques and observations about Linearity testing in order to resolve two recent versions of this task. First, we focus on the online-manipulation-resilient model introduced by Kalemaj, Raskhodnikova and Varma (Theory of Computing 2023). In this model, up to t data entries are adversarially manipulated after each query is answered. Ben-Eliezer, Kelman, Meir, and Raskhodnikova (ITCS 2024) showed an asymptotically optimal Linearity tester that is resilient to t manipulations per query, but fails if t is too large. We simplify their analysis for the regime of small t, and for larger values of t we instead use sample-based testers, as defined by Goldreich and Ron (ACM Transactions on Computation Theory 2016). A key observation is that sample-based testing is resilient to online manipulations but still achieves optimal query complexity for Linearity when t is large. We complement our result by showing that when t is very large any reasonable property, and in particular Linearity, cannot be tested at all. Second, we consider Linearity over the reals with proximity parameter ε. Fleming and Yoshida (ITCS 2020) gave a tester using O (1/ε · log (1/ε)) queries. We simplify their algorithms and modify the analysis accordingly, showing an optimal tester that only uses O (1/ε) queries. This modification works for the low-degree testers presented in Arora, Bhattacharyya, Fleming, Kelman, and Yoshida (SODA 2023) as well, resulting in optimal testers for degree-d polynomials, for any constant d. 

The online manipulation-resilient testing model, proposed by Kalemaj, Raskhodnikova and Varma (ITCS 2022 and Theory of Computing 2023), studies property testing in situations where access to the input degrades continuously and adversarially. Specifically, after each query made by the tester is answered, the adversary can intervene and either erase or corrupt t data points. In this work, we investigate a more nuanced version of the online model in order to overcome old and new impossibility results for the original model. We start by presenting an optimal tester for linearity and a lower bound for low-degree testing of Boolean functions in the original model. We overcome the lower bound by allowing batch queries, where the tester gets a group of queries answered between manipulations of the data. Our batch size is small enough so that function values for a single batch on their own give no information about whether the function is of low degree. Finally, to overcome the impossibility results of Kalemaj et al. for sortedness and the Lipschitz property of sequences, we extend the model to include t < 1, i.e., adversaries that make less than one erasure per query. For sortedness, we characterize the rate of erasures for which online testing can be performed, exhibiting a sharp transition from optimal query complexity to impossibility of testability (with any number of queries). Our online tester works for a general class of local properties of sequences. One feature of our results is that we get new (and in some cases, simpler) optimal algorithms for several properties in the standard property testing model.